# O(n^2)
# import functools
# class Solution(object):
#     def new21Game(self, n, k, maxPts):
#         base = 1 / maxPts
#         @functools.cache
#         def search(t):
#             if t >= k:
#                 if t <= n:
#                     return 1
#                 else:
#                     return 0
#             else:
#                 if t > n:
#                     return 0
#                 else:
#                     p = 0
#                     for i in range(1, maxPts + 1):
#                         p += base * search(t + i)
#                     return p
#         return search(0)
class Solution(object):
    def new21Game(self, n, k, maxPts):
        if k == 0:
            return 1
        DP = [0] * (n + 1)
        base = 1 / maxPts
        presum = 0
        for i in range(1, min(n, maxPts) + 1):
            DP[i] = base + presum * base
            if i < k:
                presum += DP[i]
        for j in range(min(n, maxPts) + 1, n + 1):
            DP[j] = max(0, presum) * base
            presum -= DP[j - maxPts]
            if j < k:
                presum += DP[j]
        return sum(DP[k:])






data = Solution()
n = 12
k = 1
maxPts = 10
print(data.new21Game(n, k, maxPts))